package cn.hesion.dataStructures.Tree.ThreadedBinaryTree;

public class ThreadedBinaryTree {
    private TreeNode root;
    private TreeNode pre = null;

    public void setRoot(TreeNode root) {
        this.root = root;
    }

    public void threadnodes() {
        this.threadnodes(root);
    }

    public void threadnodes(TreeNode node) {
        if (node == null) {
            return;
        }
        //线索化左子树
        threadnodes(node.getLeft());
        //线索化当前节点的左孩子成为前续节点
        if (node.getLeft() == null) {
            node.setLeft(pre);
            node.setLeftType(1);
        }
        //线索化当前节点的右孩子为后继节点
        if (pre != null && pre.getRight() == null){
            pre.setRight(node);
            pre.setRightType(1);
        }
        pre=node;
        //线索化右子树
        threadnodes(node.getRight());
    }

    //遍历线索化二叉树
    public void threadList(){
        TreeNode node = root;
        while(node !=null){
            //本次循环寻找leftType为1的节点，即他是某个节点的前续节点
            while (node.getLeftType() == 0){
                node = node.getLeft();
            }
            //到这里上面循环结束，则表明找到了leftType为1的节点
            //输出该节点
            System.out.println(node);
            //这次循环则是寻找后继节点
            while(node.getRightType() == 1){
                node = node.getRight();
                System.out.println(node);
            }
            //走到这里表明，后继节点的值
            node = node.getRight();
        }
    }
}
